/* 
  1 链表数据结构（动态数据结构）
  getSize
  isEmpty
  add(index, e)
  addFirst(e)
  addLast(e)
  get(index)
  getFirst()
  getLast()
  remove(index)
  removeFirst()
  removeLast()
  set(index, e)
  contains(e)
  toString
*/
class Node {
  constructor(data, next) {
    this.data = data;
    this.next = next;
  }
}

class LinkedList {
  constructor() {
    this.size = 0;
    this.dummyHead = new Node();
  }

  getSize() {
    return this.size;
  }
  isEmpty() {
    return this.size === 0;
  }

  add(index, data) {
    if (index < 0 || index > this.size) {
      throw new Error('越界');
    }

    let prev = this.dummyHead;
    for (let i = 0; i < index; i++) {
      prev = prev.next;
    }
    prev.next = new Node(data, prev.next);
    this.size++;
  }
  addFirst(data) {
    this.add(0, data);
  }
  addLast(data) {
    this.add(0, data);
  }

  get(index) {
    if (index < 0 || index >= this.size) {
      throw new Error('越界');
    }
    let cur = this.dummyHead.next;
    for (let i = 0; i < index; i++) {
      cur = cur.next;
    }
    return cur;
  }
  getFirst() {
    return this.get(0);
  }

  getLast() {
    return this.get(this.size - 1);
  }

  remove(index) {
    if (index < 0 || index >= this.size) {
      throw new Error('越界');
    }
    // 找到prev元素,改变指针即可
    let prev = this.dummyHead;
    for (let i = 0; i < index; i++) {
      prev = prev.next;
    }
    const delNode = prev.next;
    prev.next = delNode.next;
    delNode.next = null;
    this.size--;
    return delNode.data;
  }

  removeFirst() {
    return this.remove(0);
  }

  removeLast() {
    return this.remove(this.size - 1);
  }

  set(index, data) {
    if (index < 0 || index >= this.size) {
      throw new Error('越界');
    }
    let cur = this.dummyHead;
    for (let i = 0; i < index; i++) {
      cur = cur.next;
    }
    cur.data = data;
  }

  contains(data) {
    let cur = this.dummyHead.next;
    while (cur) {
      if (cur.data === data) {
        return true;
      }
      cur = cur.next;
    }
    return false;
  }

  toString() {
    let res = '';
    let cur = this.dummyHead.next;
    while (cur) {
      res += `${cur.data} --> `;
      cur = cur.next;
    }
    res += 'null';
    return res;
  }
}

const link = new LinkedList();
for (let i = 0; i < 5; i++) {
  link.addFirst(i);
  console.log(link.toString());
}
link.add(2, 222);
console.log(link.toString());
link.remove(2);
console.log(link.toString());
link.removeLast();
console.log(link.toString());
link.removeFirst();
console.log(link.toString());
